// 图的邻接表表示
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_VERTEX_NUM 20
#define INF 9999  // 用于表示没有边的情况
 
typedef int VertexType;  // 顶点类型
typedef int InfoType;    // 边的附加信息类型（如果需要）
 
// 边的定义
typedef struct ArcNode {
    int adjvex;           // 该边所指向的顶点的位置
    struct ArcNode *nextarc;  // 指向下一条边的指针
    //InfoType info;      // 边的权值（如果是带权图，则需要这个字段）
} ArcNode;
 
// 顶点的定义
typedef struct VNode {
    VertexType data;       // 顶点数据
    ArcNode *firstarc;     // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];
 
// 图的定义
typedef struct {
    AdjList vertices;     // 邻接表数组
    int vexnum, arcnum;   // 图的顶点数和边数
    int kind;             // 图的种类标志
} ALGraph;
 
// 创建图的函数
void CreateGraph(ALGraph *G) {
    int i, j, k;
    int v1, v2;
    ArcNode *arc;
 
    printf("请输入顶点数和边数：");
    scanf("%d,%d", &G->vexnum, &G->arcnum);  // 输入总顶点数和边数
 
    // 输入顶点信息
    printf("请输入各顶点的信息：\n");
    for (i = 0; i < G->vexnum; i++) {
        printf("顶点 %d: ", i + 1);
        scanf("%d", &G->vertices[i].data);  // 存入顶点表
        G->vertices[i].firstarc = NULL;     // 初始化每个顶点的第一条边为空
    }
 
    // 输入边的信息
    printf("请输入边的信息 (v1, v2)：\n");
    for (k = 0; k < G->arcnum; k++) {
        printf("边 %d (v1 v2): ", k + 1);
        scanf("%d %d", &v1, &v2);  // 输入一条边的两个顶点
 
        // 创建一个新边，并将其加入到 v1 的邻接表中
        arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = v2;  // 设置边的指向顶点
        arc->nextarc = G->vertices[v1-1].firstarc;  // 将新边指向 v1 当前的第一条边
        G->vertices[v1-1].firstarc = arc;  // 更新 v1 顶点的第一条边
 
        // 由于是无向图，需要在 v2 顶点的邻接表中也添加一条边
        arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = v1;  // 设置边的指向顶点
        arc->nextarc = G->vertices[v2-1].firstarc;  // 将新边指向 v2 当前的第一条边
        G->vertices[v2-1].firstarc = arc;  // 更新 v2 顶点的第一条边
    }
}
 
// 打印图的邻接表
void PrintGraph(ALGraph G) {
    int i;
    ArcNode *arc;
 
    printf("图的邻接表：\n");
    for (i = 0; i < G.vexnum; i++) {
        printf("顶点 %d: ", G.vertices[i].data);
        arc = G.vertices[i].firstarc;  // 获取当前顶点的第一条边
        while (arc != NULL) {
            printf("%d ", arc->adjvex);  // 打印边指向的顶点
            arc = arc->nextarc;  // 移动到下一条边
        }
        printf("\n");
    }
}
 
int main() {
    ALGraph G;
     
    // 创建图
    CreateGraph(&G);
     
    // 打印图的邻接表
    PrintGraph(G);
 
    return 0;
}
